/*
 * @lc app=leetcode.cn id=1414 lang=cpp
 *
 * [1414] 和为 K 的最少斐波那契数字数目
 */

// @lc code=start
class Solution
{
public:
    int findMinFibonacciNumbers(int k)
    {
        vector<int> fib = {1};
        int a = 1, b = 1;
        while (a + b <= k)
        {
            int c = a + b;
            fib.push_back(c);
            a = b;
            b = c;
        }

        int ans = 0;
        while (k > 0)
        {
            if (k >= fib.back())
            {
                k -= fib.back();
                ans++;
            }
            else
            {
                fib.pop_back();
            }
        }

        return ans;
    }
};
// @lc code=end
